{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8.4 Bucket sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.4-1\n",
    "\n",
    "> Using Figure 8.4 as a model, illustrate the operation of BUCKET-SORT on the array $A = \\left \\langle.79, .13, .16, .64, .39, .20, .89, .53, .71, .42\\right \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| R | |\n",
    "|:-:|:--|\n",
    "| 0 ||\n",
    "| 1 |.13 .16|\n",
    "| 2 |.20|\n",
    "| 3 |.39|\n",
    "| 4 |.42|\n",
    "| 5 |.53|\n",
    "| 6 |.64|\n",
    "| 7 ||\n",
    "| 8 |.79 .71|\n",
    "| 9 |.89|\n",
    "\n",
    "$A = \\left \\langle.13, .16, .20, .39, .42, .53, .64, .71, .79, .89\\right \\rangle$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.4-2\n",
    "\n",
    "> Explain why the worst-case running time for bucket sort is $\\Theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time $O(n \\lg n)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Worst: all the elements falls in one bucket, $\\Theta(n ^ 2)$ sorting.\n",
    "\n",
    "Change: use merge sort in each bucket."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.4-3\n",
    "\n",
    "> Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $\\text{E}[X^2]$? What is $\\text{E}^2[X]$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\text{E}[X] = 2 \\cdot \\frac{1}{4} + 1 \\cdot \\frac{1}{2} + 0 \\cdot \\frac{1}{4} = 1\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\text{E}[X^2] = 4 \\cdot \\frac{1}{4} + 1 \\cdot \\frac{1}{2} + 0 \\cdot \\frac{1}{4} = 1.5\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\text{E}^2[X] = \\text{E}[X] \\cdot \\text{E}[X] = 1 \\cdot 1 = 1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.4-4 $\\star$\n",
    "\n",
    "> We are given $n$ points in the unit circle, $p_i = (xi, yi)$, such that $0 < x_i^2 + y_i^2 \\le 1$ for $i = 1,2, \\dots ,n$. Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design an algorithm with an average-case running time of $\\Theta(n)$ to sort the $n$ points by their distances $d_i = \\sqrt{x_i^2+y_i^2}$ from the origin. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bucket sort by radius, \n",
    "\n",
    "$$\n",
    "\\pi r_i^2 = \\frac{i}{10} \\cdot \\pi 1^2\n",
    "$$\n",
    "\n",
    "$$\n",
    "r_i = \\sqrt{\\frac{i}{10}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.4-5 $\\star$\n",
    "\n",
    "> A __*probability distribution function*__ $P(x)$ for a random variable $X$ is defined by $P(x) = \\text{Pr}\\{X \\le x\\}$. Suppose that we draw a list of $n$ random variables $X_1,X_2, \\dots ,X_n$ from a continuous probability distribution function $P$ that is computable in $O(1)$ time. Give an algorithm that sorts these numbers in linear average-case time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bucket sort by $p_i$,\n",
    "\n",
    "$$\n",
    "P(p_i) = \\frac{i}{10}\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
